翻訳と辞書 Words near each other ・ Hirschau (Tübingen) ・ Hirschbach ・ Hirschbach (Gersprenz) ・ Hirschbach im Mühlkreis ・ Hirschbach, Bavaria ・ Hirschbach, Lower Austria ・ Hirschbeck ・ Hirschberg ・ Hirschberg (Allgäu Alps) ・ Hirschberg (Bavaria) ・ Hirschberg (Kaufungen Forest) ・ Hirschberg (Lower Bavaria) ・ Hirschberg (Ohlstadt) ・ Hirschberg an der Bergstraße ・ Hirschberg test ・ Hirschberg's algorithm ・ Hirschberg, Rhineland-Palatinate ・ Hirschberg, Thuringia ・ Hirschberger Bach ・ Hirschdale, California ・ Hirschegg ・ Hirschel Levin ・ Hirschengraben Tunnel ・ Hirschenstein ・ Hirschenstein (Saxony) ・ Hirschfeld ・ Hirschfeld Eddy Foundation ・ Hirschfeld Industries ・ Hirschfeld Wildlife Park ・ Hirschfeld, Brandenburg Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Hirschberg's algorithm ： ウィキペディア英語版 Hirschberg's algorithm In computer science, Hirschberg's algorithm, named after its inventor, Dan Hirschberg, is a dynamic programming algorithm that finds the optimal sequence alignment between two strings. Optimality is measured with the Levenshtein distance, defined to be the sum of the costs of insertions, replacements, deletions, and null actions needed to change one string into the other. Hirschberg's algorithm is simply described as a divide and conquer version of the Needleman–Wunsch algorithm.〔(Hirschberg's algorithm )〕 Hirschberg's algorithm is commonly used in computational biology to find maximal global alignments of DNA and protein sequences. ==Algorithm information== Hirschberg's algorithm is a generally applicable algorithm for optimal sequence alignment. BLAST and FASTA are suboptimal heuristics. If ''x'' and ''y'' are strings, where length(''x'') = ''n'' and length(''y'') = ''m'', the Needleman-Wunsch algorithm finds an optimal alignment in O(''nm'') time, using O(''nm'') space. Hirschberg's algorithm is a clever modification of the Needleman-Wunsch Algorithm which still takes O(''nm'') time, but needs only O(min) space.〔http://www.cs.tau.ac.il/~rshamir/algmb/98/scribe/html/lec02/node10.html〕 One application of the algorithm is finding sequence alignments of DNA or protein sequences. It is also a space-efficient way to calculate the longest common subsequence between two sets of data such as with the common diff tool. The Hirschberg algorithm can be derived from the Needleman-Wunsch algorithm by observing that: # one can compute the optimal alignment score by only storing the current and previous row of the Needleman-Wunsch score matrix; # if $(Z,W)\; =\; \backslash operatorname(X,Y)$ is the optimal alignment of $(X,Y)$, and $X\; =\; X^l\; +\; X^r$ is an arbitrary partition of $X$, there exists a partition $Y^l\; +\; Y^r$ of $Y$ such that $\backslash operatorname(X,Y)\; =\; \backslash operatorname(X^l,Y^l)\; +\; \backslash operatorname(X^r,Y^r)$. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Hirschberg's algorithm」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.